We have developed algorithms for comparison of protein three dimensional structures. The "VAST" algorithm, for "vector alignment search tool," identifies substructures similarities rapidly by comparing the types, connectivity, and relative orientations secondary structure elements. Work has focused in three areas: 1) definition of the threshold similarity statistic, 2) validation of sensitivity and specificity, and 3) development of statistical criteria for "optimal" residue-by-residue alignment. VAST ranks substructure similarities by chance-occurrence likelihood. This is calculated as the product of the probabilities that independent element-pair superposition residuals would be observed by chance, as determined by reference to an empirical distribution based on random draws of element pairs in the structural database. A threshold statistic is given as the product of the greatest substructure likelihood and the number of possible substructure choices, as determined by a combinatorial formula involving the number of discrete elements present in each protein. If small, this value is interpretable directly as a test statistic or p-value for significant similarity. VAST has been tested by an all-against-all analysis of known structures. Sensitivity with respect to BLAST "hits" is 99.5%. Specificity in test cases from the literature appears perfect, and comparison to existing non- statistical methods indicates fewer hits, with omissions being low-score marginal similarities. Residue-residue alignments are now constructed by a Gibb's sampling scheme, which proved more efficient than Metropolis sampling. Significance of alternative residue alignments is evaluated by reference to an empirical distribution of superposition residuals in random alignments, to identify the most surprising one. An analytical density function fitted to empirical random-element self comparison residuals proved superior to a substructure-specific null model in reproducing literature expert alignments, and is in addition faster. The significance of this work will be in extending the horizon to which evolutionary relationship may be detected, by employing structure comparison in place of sequence comparison alone. The results have been made available to biologists as "structural neighbors" in the "Entrez" browser.